//  括号匹配 时间复杂度为O(n)
function isMatch(left: string, right: string) {
    if (left === '{' && right === '}') return true;
    if (left === '[' && right === ']') return true;
    if (left === '(' && right === ')') return true;
    return false;
}

function matchBracket(str: string): boolean {
    const length = str.length
    if (length === 0) return true
    const stack:string[] = []
    const leftSymbold = '{[('
    const rightSymbold = '}])';
    for (let i = 0; i < length; i++) {
        const s = str[i]
        if (leftSymbold.includes(s)) {
            // 左括号 压栈
            stack.push(s)
        } else if (rightSymbold.includes(s)) {
            // 右括号 判断栈顶 （是否出栈）
            const top = stack[stack.length - 1]
            if (isMatch(top, s)) {
                stack.pop()
            } else {
                return false
            }
        }
    }
    return stack.length === 0
}

const str = '{a(b[c]d)e}f'
console.log(matchBracket(str))
